<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>C/C&#43;&#43;手撕哈希表详解 - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="C&#43;&#43;手撕哈希表详解"><meta property="og:title" content="C/C&#43;&#43;手撕哈希表详解" />
<meta property="og:description" content="C&#43;&#43;手撕哈希表详解" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-02-16T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-02-16T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="C/C&#43;&#43;手撕哈希表详解"/>
<meta name="twitter:description" content="C&#43;&#43;手撕哈希表详解"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" /><link rel="prev" href="https://acking-you.github.io/posts/java%E8%BF%9E%E6%8E%A5%E6%95%B0%E6%8D%AE%E5%BA%93/" /><link rel="next" href="https://acking-you.github.io/posts/%E9%AA%91%E5%A3%AB%E5%9C%A8%E6%A3%8B%E7%9B%98%E4%B8%8A%E7%9A%84%E6%A6%82%E7%8E%87dp%E6%A3%8B%E7%9B%98%E6%A6%82%E7%8E%87%E9%A2%98/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "C/C++手撕哈希表详解",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/c\u002b\u002b%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3\/"
        },"genre": "posts","keywords": "C\/C\u002b\u002b手撕哈希表详解","wordcount":  4501 ,
        "url": "https:\/\/acking-you.github.io\/posts\/c\u002b\u002b%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3\/","datePublished": "2022-02-16T00:00:00+00:00","dateModified": "2022-02-16T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "C++手撕哈希表详解"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center, https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center 1.5x, https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center"
        title="C&#43;&#43;手撕哈希表详解" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">C/C&#43;&#43;手撕哈希表详解</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E6%89%8B%E5%86%99%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><i class="far fa-folder fa-fw"></i>手写数据结构</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-02-16">2022-02-16</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 4501 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 9 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#哈希表的理论知识">哈希表的理论知识</a>
      <ul>
        <li><a href="#哈希表的定义">哈希表的定义</a></li>
        <li><a href="#桶数组">桶数组</a></li>
        <li><a href="#散列函数">散列函数</a></li>
      </ul>
    </li>
    <li><a href="#hashmap实现">HashMap实现</a>
      <ul>
        <li><a href="#类型定义键值对以及对应节点">类型定义（键值对以及对应节点）</a></li>
        <li><a href="#哈希表的数据">哈希表的数据</a></li>
        <li><a href="#初始化方法构造方法">初始化方法（构造方法）</a></li>
        <li><a href="#根据散列函数得到位置">根据散列函数得到位置</a></li>
        <li><a href="#put方法">put方法</a></li>
        <li><a href="#扩容方法">扩容方法</a></li>
        <li><a href="#get方法">get方法</a></li>
        <li><a href="#完整代码">完整代码</a></li>
        <li><a href="#测试leetcode-1两数之和">测试：LeetCode 1.两数之和</a></li>
      </ul>
    </li>
    <li><a href="#总结">总结</a></li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h1 id="关于实现源码">关于实现源码</h1>
<p>实现源码仓库在线查看链接：</p>
<p><a href="https://github1s.com/ACking-you/my_tiny_stl/blob/HEAD/%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E5%B0%81%E8%A3%85/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%B1%BB/C%E8%AF%AD%E8%A8%80%E5%AE%9E%E7%8E%B0/HashMap_C.h#L23-L31" target="_blank" rel="noopener noreffer">C语言实现</a></p>
<p><a href="https://github1s.com/ACking-you/my_tiny_stl/blob/HEAD/%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E5%B0%81%E8%A3%85/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%B1%BB/C&#43;&#43;%20unordered_map%E5%AE%9E%E7%8E%B0/unordered_map.hpp" target="_blank" rel="noopener noreffer">C++实现</a></p>
<h2 id="哈希表的理论知识">哈希表的理论知识</h2>
<h3 id="哈希表的定义">哈希表的定义</h3>
<p>哈希表也叫散列表，我们先来看看哈希表的定义：</p>
<blockquote>
<p>哈希表是保存键值映射关系的查找表，通过关键字可以很快找到对应的值。</p>
</blockquote>
<p>简单说来说，哈希表由两个要素构成：<code>桶数组</code> 和 <code>散列函数</code>（哈希函数）。</p>
<ul>
<li>桶数组：用于存储键值对的空间。</li>
<li>散列函数：用于给键值对在桶数组中的位置指路。</li>
</ul>
<h3 id="桶数组">桶数组</h3>
<p>我们可能知道，有一类基础的数据结构 <code>线性表</code>，而线性表又分两种，<code>数组</code> 和 <code>链表</code>。</p>
<p>哈希表数据结构里，存储元素的数据结构就是数组，数组里的每个单元都可以想象成一个 <code>桶</code>（Bucket）。</p>
<p>而我们每次都是把我们需要存入的键值对加入到这样的桶子中。</p>
<h3 id="散列函数">散列函数</h3>
<p>我们需要在元素和 <code>桶数组</code> 对应位置建立一种映射映射关系，这种映射关系就是 <code>散列函数</code> ，也可以叫哈希函数。</p>
<p>比如我们平时生活中，碰到排队型的时候，都需要根据高矮来进行一定的队形调整，这个调整过程也可以看做是散列函数的一种体现。</p>
<h4 id="散列函数的构造">散列函数的构造</h4>
<p>散列函数有很多类，这其中的奥妙来自于数学，而不是我们程序员需要过于操心的事情。</p>
<p>在Java语言中只要是继承自Object类的所有类都有默认的一个 <code>hashcode()</code> 方法，而对于具体过程我们不需要多想，我们来看看最常用的字符串的哈希过程：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">strHashcode</span><span class="p">(</span><span class="kt">char</span> <span class="o">*</span><span class="n">key</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">size_t</span> <span class="n">hash</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">size_t</span> <span class="n">index</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">key</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">!=</span> <span class="sc">&#39;\0&#39;</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">hash</span> <span class="o">=</span> <span class="n">hash</span> <span class="o">*</span> <span class="mi">31</span> <span class="o">+</span> <span class="n">key</span><span class="p">[</span><span class="n">index</span><span class="o">++</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">hash</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p>很明显得出的 hashcode 是一个以31为底的次方数，关于为什么以31为底，我这里简单的描述一下：</p>
<ol>
<li>以31为底能很快得出比较散且比较大的二进制码（底层的01串），这样结合子掩码的与运算有利于减少哈希冲突的产生。</li>
<li><code>31 * i ==  (i &lt;&lt; 5) - i</code>  因为这个等式的成立使得运算性能也有很大的提升。（编译器一般会对 <code>31*i</code> 进行优化的）</li>
</ol>
<p>更多细节看看这篇文章：<a href="https://blog.csdn.net/mxw2552261/article/details/91349677" target="_blank" rel="noopener noreffer">关于为什么选31</a></p>
<h4 id="扰动函数-和-按位与">扰动函数 和 按位与</h4>
<p>我们通过散列函数得到一堆 01 串后，我们该怎么做？</p>
<p>接下来一般就是通过和桶数组的长度取余然后得到对应的位置进行插入。这样虽然也可以，但我们有更好的方式进行替代，那就是位运算。</p>
<p>既然要讲位运算，那么我先讲讲一个二进制串。
在只有一个 1 的二进制串里面，我们对它再减去 1 的时候，我们很快得到它的低位掩码。
比如：
<code>0001000 - 1 = 0000111</code>，得到的 <code>0000111</code> 有什么用处呢？</p>
<p>如果我们把一个 <code>hashcode</code> 和这个数进行按位与，则得到的结果肯定是介于 <code>000~111</code> 之间，也就是 <code>0~7</code> 之间，这个时候我们思考一下，如果把这个 <code>0001000</code> 看做是桶数组的长度，那么这个按位与的结果就可以当做需要存入的桶的具体位置了。</p>
<p>基于这个理论，我们只要桶数组长度是 <code>2的倍数</code> 则 <code>hashcode%size</code> 可用 <code>hashcode&amp;(size-1)</code> 来替代。</p>
<p>这样做有以下好处：</p>
<ol>
<li>位运算的性能更好。</li>
<li>便于控制 hashcode 最终得出的结果，有些时候我们得到的 <code>hashcode不够均匀</code> 高位的1比较多，而低位的1比较少，这个时候可以利用 <code>hashcode^(hashcode&gt;&gt;16)</code> 进行一定程度的打散，而这个打散的过程我们一般把它叫做 <code>扰动函数</code> 。</li>
</ol>
<h4 id="哈希冲突">哈希冲突</h4>
<blockquote>
<p>当出现键值运算结果得到的桶子位置是同一个的时候便产生了哈希冲突。</p>
</blockquote>
<p>而解决哈希冲突的方案一般有以下三种：
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/98f732dca9f348d980832f146c717b7f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/98f732dca9f348d980832f146c717b7f.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/98f732dca9f348d980832f146c717b7f.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/98f732dca9f348d980832f146c717b7f.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/98f732dca9f348d980832f146c717b7f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/98f732dca9f348d980832f146c717b7f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
<strong>链地址法</strong>
一旦发生哈希冲突，直接生成链表往后继续延伸。
<strong>开放地址法</strong>
简单来说就是给冲突的元素再在桶数组里找到一个空闲的位置。
而常用采用的方法有：</p>
<ol>
<li>线性探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置。</li>
<li>平方探查法: 从冲突的位置x开始，第一次增加 <code>1^2</code> 个位置，第二次增加 <code>2^2</code>…，直至找到空闲的位置。</li>
<li>双散列函数探查法</li>
</ol>
<p>&hellip;&hellip;
<strong>再哈希法</strong></p>
<p>再哈希法完全可以配备以上两类方法进行使用。</p>
<p>当然也可单独使用，单独使用的话就行配备多个哈希函数，一个不行的话换另一个哈希函数，直到不产生哈希冲突为止。</p>
<p><strong>最终的选择：</strong></p>
<p>而我们常用的是 <code>链地址法 + 再哈希</code> ，为了能够尽量减少内存空间的使用，我们默认从容量为 16 的桶数组开始，一旦装入的键值对超过 <code>capacity * factor</code> 个时，我们进行一次两倍的（左移1位）扩容，而由于扩容会导致 <code>capacity</code> 改变，所以通过 <code>哈希函数 + 与运算</code> 得出的位置也会出错，故需要经过 <code>再哈希</code> 。</p>
<p>我们其实可以继续细想，我们左移一位后，得出的结果再减一，它也仅仅多出一位掩码，而我们的 <code>hashcode</code> 只要在这一位上为 0 则最后得到的桶位置不会有任何改变，只有在这一位上为 1 的才会发生改变，所以根据这个特点，Java 8 进行了一些优化，更厉害的优化方式在于，只要链比较长，它还会转红黑树（这就在我的能力范围之外了）。</p>
<p>以上内容参考的文章为：<a href="https://blog.csdn.net/zhengwangzw/article/details/104889549" target="_blank" rel="noopener noreffer">一个HashMap和面试官扯了半小时</a></p>
<h2 id="hashmap实现">HashMap实现</h2>
<h3 id="类型定义键值对以及对应节点">类型定义（键值对以及对应节点）</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="cp">#define DEFAULT_CAPACITY 16 </span><span class="c1">//初始的表长
</span><span class="c1"></span><span class="cp">#define DEFAULT_FACTOR 0.75f </span><span class="c1">//初始的装载因子
</span><span class="c1"></span><span class="cm">/*类型定义 和 装载因子初始化*/</span>
<span class="k">typedef</span> <span class="kt">int</span> <span class="n">key_t</span><span class="p">;</span>
<span class="k">typedef</span> <span class="kt">int</span> <span class="n">val_t</span><span class="p">;</span>
<span class="k">static</span> <span class="k">const</span> <span class="kt">float</span> <span class="n">factor</span> <span class="o">=</span> <span class="n">DEFAULT_FACTOR</span><span class="p">;</span> <span class="c1">//装载因子
</span><span class="c1"></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">node</span> <span class="p">{</span><span class="c1">//每个哈希表的键值对
</span><span class="c1"></span>    <span class="n">key_t</span> <span class="n">key</span><span class="p">;</span>
    <span class="n">val_t</span> <span class="n">val</span><span class="p">;</span>
    <span class="k">struct</span> <span class="n">node</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="p">}</span> <span class="n">Node</span><span class="p">;</span>
</code></pre></div><p><strong>C++</strong></p>
<blockquote>
<p>全程用的泛型模板
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/7e5ae0b45db147b6ac179969ad2e8854.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/7e5ae0b45db147b6ac179969ad2e8854.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/7e5ae0b45db147b6ac179969ad2e8854.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/7e5ae0b45db147b6ac179969ad2e8854.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/7e5ae0b45db147b6ac179969ad2e8854.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/7e5ae0b45db147b6ac179969ad2e8854.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<h3 id="哈希表的数据">哈希表的数据</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="k">typedef</span> <span class="k">struct</span> <span class="p">{</span>
    <span class="n">size_t</span> <span class="n">size</span><span class="p">;</span>       <span class="c1">//记录已经存下的键值对数目
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">capacity</span><span class="p">;</span>   <span class="c1">//记录表长
</span><span class="c1"></span>    <span class="n">Node</span> <span class="o">**</span><span class="n">buckets</span><span class="p">;</span> <span class="c1">//桶子：用于记录的哈希桶，桶子中每个元素是Node*
</span><span class="c1"></span><span class="p">}</span> <span class="n">HashMap</span><span class="p">;</span>
</code></pre></div><p><strong>C++</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/622883b95743448ab199986046100179.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/622883b95743448ab199986046100179.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/622883b95743448ab199986046100179.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/622883b95743448ab199986046100179.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/622883b95743448ab199986046100179.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/622883b95743448ab199986046100179.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="初始化方法构造方法">初始化方法（构造方法）</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="n">HashMap</span> <span class="o">*</span><span class="nf">init</span><span class="p">()</span> <span class="p">{</span>    <span class="c1">//初始化得到一个哈希表
</span><span class="c1"></span>    <span class="n">HashMap</span> <span class="o">*</span><span class="n">ret</span> <span class="o">=</span> <span class="p">(</span><span class="n">HashMap</span> <span class="o">*</span><span class="p">)</span> <span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">HashMap</span><span class="p">));</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">ret</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="n">ret</span><span class="o">-&gt;</span><span class="n">size</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">ret</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">=</span> <span class="n">DEFAULT_CAPACITY</span><span class="p">;</span>
    <span class="n">ret</span><span class="o">-&gt;</span><span class="n">buckets</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span> <span class="o">**</span><span class="p">)</span> <span class="n">calloc</span><span class="p">(</span><span class="n">DEFAULT_CAPACITY</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="p">));</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">ret</span><span class="o">-&gt;</span><span class="n">buckets</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">ret</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><p><strong>C++</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/dd3e94a38a934f0aaa40721daa77aa63.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/dd3e94a38a934f0aaa40721daa77aa63.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/dd3e94a38a934f0aaa40721daa77aa63.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/dd3e94a38a934f0aaa40721daa77aa63.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/dd3e94a38a934f0aaa40721daa77aa63.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/dd3e94a38a934f0aaa40721daa77aa63.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="根据散列函数得到位置">根据散列函数得到位置</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">getHashcode</span><span class="p">(</span><span class="n">key_t</span> <span class="n">key</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">return</span> <span class="n">key</span> <span class="o">^</span> <span class="p">(</span><span class="n">key</span> <span class="o">&gt;&gt;</span> <span class="mi">16</span><span class="p">);</span><span class="c1">//这是32位数的扰动函数
</span><span class="c1"></span><span class="p">}</span>

<span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">getIndex</span><span class="p">(</span><span class="n">key_t</span> <span class="n">key</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">bucket_size</span><span class="p">)</span> <span class="p">{</span><span class="c1">//由于bucketsize一定是2的次方，所以size-1和key相与得到的就是下标
</span><span class="c1"></span>    <span class="k">return</span> <span class="n">getHashcode</span><span class="p">(</span><span class="n">key</span><span class="p">)</span> <span class="o">&amp;</span> <span class="p">(</span><span class="n">bucket_size</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><p><strong>C++</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/d2d3a86c62aa4a9790e8e8c214e12e6e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/d2d3a86c62aa4a9790e8e8c214e12e6e.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/d2d3a86c62aa4a9790e8e8c214e12e6e.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/d2d3a86c62aa4a9790e8e8c214e12e6e.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/d2d3a86c62aa4a9790e8e8c214e12e6e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/d2d3a86c62aa4a9790e8e8c214e12e6e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="put方法">put方法</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">put</span><span class="p">(</span><span class="n">HashMap</span> <span class="o">*</span><span class="n">map</span><span class="p">,</span> <span class="n">key_t</span> <span class="n">key</span><span class="p">,</span> <span class="n">val_t</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">map</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="c1">//判断是否需要扩容
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">size</span> <span class="o">&gt;=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">*</span> <span class="n">factor</span><span class="p">)</span> <span class="n">resize</span><span class="p">(</span><span class="n">map</span><span class="p">);</span>
    <span class="n">putVal</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">val</span><span class="p">,</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">size</span><span class="p">,</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">);</span>
<span class="p">}</span>



<span class="k">static</span> <span class="kt">void</span> <span class="nf">putVal</span><span class="p">(</span><span class="n">key_t</span> <span class="n">key</span><span class="p">,</span> <span class="n">val_t</span> <span class="n">val</span><span class="p">,</span> <span class="n">Node</span> <span class="o">**</span><span class="n">buckets</span><span class="p">,</span> <span class="n">size_t</span> <span class="o">*</span><span class="n">returnSize</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">bucketSize</span><span class="p">)</span> <span class="p">{</span>
    <span class="c1">//获取位置
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">index</span> <span class="o">=</span> <span class="n">getIndex</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">bucketSize</span><span class="p">);</span>
    <span class="n">Node</span> <span class="o">*</span><span class="n">node</span> <span class="o">=</span> <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">node</span> <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span><span class="c1">//插入位置为空
</span><span class="c1"></span>        <span class="n">node</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="p">)</span> <span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span><span class="p">));</span>
        <span class="n">assert</span><span class="p">(</span><span class="n">node</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span> <span class="o">=</span> <span class="n">key</span><span class="p">;</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">node</span><span class="p">;</span>
        <span class="p">(</span><span class="o">*</span><span class="n">returnSize</span><span class="p">)</span><span class="o">++</span><span class="p">;</span>    <span class="c1">//哈希表内的元素增加
</span><span class="c1"></span>        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="c1">//插入位置不为空，说明发生冲突，使用链地址法，遍历链表
</span><span class="c1"></span>    <span class="k">while</span> <span class="p">(</span><span class="n">node</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
        <span class="c1">//如果key相同就覆盖
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">node</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
            <span class="k">return</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">node</span> <span class="o">=</span> <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="c1">//当前的key不在链表中，则插入链表头部
</span><span class="c1"></span>    <span class="n">Node</span> <span class="o">*</span><span class="n">newNode</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="p">)</span> <span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span><span class="p">));</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">newNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="n">newNode</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
    <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">newNode</span><span class="p">;</span>
    <span class="p">(</span><span class="o">*</span><span class="n">returnSize</span><span class="p">)</span><span class="o">++</span><span class="p">;</span> <span class="c1">//哈希表内元素增加
</span><span class="c1"></span><span class="p">}</span>
</code></pre></div><p><strong>C++</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/d9ad7729b6794daf842d47f37f1aa2ef.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/d9ad7729b6794daf842d47f37f1aa2ef.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/d9ad7729b6794daf842d47f37f1aa2ef.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/d9ad7729b6794daf842d47f37f1aa2ef.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/d9ad7729b6794daf842d47f37f1aa2ef.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/d9ad7729b6794daf842d47f37f1aa2ef.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="扩容方法">扩容方法</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="k">static</span> <span class="kt">void</span> <span class="nf">resize</span><span class="p">(</span><span class="n">HashMap</span> <span class="o">*</span><span class="n">map</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">&lt;&lt;=</span> <span class="mi">1</span><span class="p">;</span>            <span class="c1">//扩大两倍容量，相当于左移一位
</span><span class="c1"></span>    <span class="n">Node</span> <span class="o">**</span><span class="n">tmp</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">;</span>     <span class="c1">//存下之前的内存地址
</span><span class="c1"></span>    <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span> <span class="o">**</span><span class="p">)</span> <span class="n">calloc</span><span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="p">));</span> <span class="c1">//重新分配
</span><span class="c1"></span>    <span class="n">assert</span><span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="n">rehash</span><span class="p">(</span><span class="n">map</span><span class="p">,</span> <span class="n">tmp</span><span class="p">);</span><span class="c1">//重新哈希处理
</span><span class="c1"></span>    <span class="n">free</span><span class="p">(</span><span class="n">tmp</span><span class="p">);</span>                                          <span class="c1">//释放之前的内存
</span><span class="c1"></span><span class="p">}</span>


<span class="k">static</span> <span class="kt">void</span> <span class="nf">rehash</span><span class="p">(</span><span class="n">HashMap</span> <span class="o">*</span><span class="n">map</span><span class="p">,</span> <span class="n">Node</span> <span class="o">**</span><span class="n">preTable</span><span class="p">)</span> <span class="p">{</span><span class="c1">//采取java1.7的方式进行rehash也就是最简单直接的直接重新哈希插入
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">preCap</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="c1">//改变前的有效区域
</span><span class="c1"></span>    <span class="k">for</span> <span class="p">(</span><span class="n">size_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">preCap</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">preTable</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span><span class="c1">//判断对应的key是否需要重新换位置,如果对最新掩码多出来的1敏感则需要rehash
</span><span class="c1"></span>            <span class="n">Node</span> <span class="o">*</span><span class="n">preNode</span><span class="p">;</span>
            <span class="n">Node</span> <span class="o">*</span><span class="n">curNode</span> <span class="o">=</span> <span class="n">preTable</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">curNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">preNode</span> <span class="o">=</span> <span class="n">curNode</span><span class="p">;</span>
                <span class="n">curNode</span> <span class="o">=</span> <span class="n">curNode</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
                <span class="n">insert</span><span class="p">(</span><span class="n">map</span><span class="p">,</span> <span class="n">preNode</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p><strong>C++</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/69c7d11c417346fd8bfeb910d7f3739e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/69c7d11c417346fd8bfeb910d7f3739e.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/69c7d11c417346fd8bfeb910d7f3739e.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/69c7d11c417346fd8bfeb910d7f3739e.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/69c7d11c417346fd8bfeb910d7f3739e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/69c7d11c417346fd8bfeb910d7f3739e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h3 id="get方法">get方法</h3>
<p><strong>C</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="n">val_t</span> <span class="o">*</span><span class="nf">get</span><span class="p">(</span><span class="n">HashMap</span> <span class="o">*</span><span class="n">map</span><span class="p">,</span> <span class="n">key_t</span> <span class="n">key</span><span class="p">)</span> <span class="p">{</span><span class="c1">//前面的写好后，那么get就很好写了
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">index</span> <span class="o">=</span> <span class="n">getIndex</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">);</span>
    <span class="n">Node</span> <span class="o">*</span><span class="n">node</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">node</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="o">&amp;</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="n">node</span> <span class="o">=</span> <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="nb">NULL</span><span class="p">;</span><span class="c1">//没找到返回NULL指针
</span><span class="c1"></span><span class="p">}</span>
</code></pre></div><p><strong>C++</strong></p>
<blockquote>
<p>C++标准中主要采用重载下标运算符的方式进行get。
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/8614bc21828a461ebcfb9e5f787aff02.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/8614bc21828a461ebcfb9e5f787aff02.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/8614bc21828a461ebcfb9e5f787aff02.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/8614bc21828a461ebcfb9e5f787aff02.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/8614bc21828a461ebcfb9e5f787aff02.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/8614bc21828a461ebcfb9e5f787aff02.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<h3 id="完整代码">完整代码</h3>
<p><a href="https://github1s.com/ACking-you/my_tiny_stl/blob/HEAD/%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E5%B0%81%E8%A3%85/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%B1%BB/C%E8%AF%AD%E8%A8%80%E5%AE%9E%E7%8E%B0/HashMap_C.h" target="_blank" rel="noopener noreffer">C完整代码</a>
<a href="https://github1s.com/ACking-you/my_tiny_stl/blob/HEAD/%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E5%B0%81%E8%A3%85/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%B1%BB/C&#43;&#43;%20unordered_map%E5%AE%9E%E7%8E%B0/unordered_map.hpp" target="_blank" rel="noopener noreffer">C++完整代码</a></p>
<h3 id="测试leetcode-1两数之和">测试：LeetCode 1.两数之和</h3>
<ul>
<li>这效率在用C语言哈希表的方法里面应该是无敌的存在了。。。试了下比UT_HASH还要快一些☺
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/e352e24a1997411b8e56db66b9c1a599.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/e352e24a1997411b8e56db66b9c1a599.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/e352e24a1997411b8e56db66b9c1a599.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/e352e24a1997411b8e56db66b9c1a599.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/e352e24a1997411b8e56db66b9c1a599.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/e352e24a1997411b8e56db66b9c1a599.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
再看看之前写的比较烂的哈希表的效率😂
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/af96cad501e647c6a477733d85d5ab9a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/af96cad501e647c6a477733d85d5ab9a.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/af96cad501e647c6a477733d85d5ab9a.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/af96cad501e647c6a477733d85d5ab9a.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/af96cad501e647c6a477733d85d5ab9a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/af96cad501e647c6a477733d85d5ab9a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" />
<strong>测试源码：</strong></li>
</ul>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="c1">//
</span><span class="c1">// Created by L_B__ on 2021/11/24.
</span><span class="c1">//
</span><span class="c1">//底层的表长都用2的次方，然后-1后可以得到低位掩码
</span><span class="c1">//该设计理念急于java1.7的源代码，本来是想基于1.8的实现，
</span><span class="c1">// 因为1.8巧妙太多，比如对rehash尽量能不动的就不动，再比如对于链比较长的结构直接转红黑树。可惜能力不能及
</span><span class="c1"></span><span class="cm">/**
</span><span class="cm"> * 简单说明：static修饰的函数为单文件的中间委托功能函数，不对外公开
</span><span class="cm"> * 简单的功能函数介绍：
</span><span class="cm"> * init()得到一个默认表长的哈希表
</span><span class="cm"> * put()插入键值，内部自动进行内存的申请
</span><span class="cm"> * get()得到key对应的val的地址，若不存在该键值对返回NULL
</span><span class="cm"> * insert()外界已经分配好node的内存和key&amp;val对，进行哈希运算后直接插入即可
</span><span class="cm"> * destroy()把整个哈希表牵扯的所有内存释放
</span><span class="cm"> * **/</span>
<span class="cp">#include</span> <span class="cpf">&lt;assert.h&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;stdlib.h&gt;</span><span class="cp">
</span><span class="cp">#ifndef MY_TINY_STL_HASHMAP_C_H
</span><span class="cp">#define MY_TINY_STL_HASHMAP_C_H
</span><span class="cp">#define DEFAULT_CAPACITY 128 </span><span class="c1">//初始的表长
</span><span class="c1"></span><span class="cp">#define DEFAULT_FACTOR 0.75f </span><span class="c1">//初始的装载因子
</span><span class="c1"></span><span class="cm">/*类型定义 和 装载因子初始化*/</span>
<span class="k">typedef</span> <span class="kt">int</span> <span class="n">key_t</span><span class="p">;</span>
<span class="k">typedef</span> <span class="kt">int</span> <span class="n">val_t</span> <span class="p">;</span>
<span class="k">static</span> <span class="k">const</span> <span class="kt">float</span> <span class="n">factor</span> <span class="o">=</span> <span class="n">DEFAULT_FACTOR</span><span class="p">;</span> <span class="c1">//装载因子
</span><span class="c1"></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">node</span><span class="p">{</span><span class="c1">//每个哈希表的键值对
</span><span class="c1"></span>    <span class="n">key_t</span> <span class="n">key</span><span class="p">;</span>
    <span class="n">val_t</span> <span class="n">val</span><span class="p">;</span>
    <span class="k">struct</span> <span class="n">node</span><span class="o">*</span> <span class="n">next</span><span class="p">;</span>
<span class="p">}</span><span class="n">Node</span><span class="p">;</span>
<span class="k">typedef</span> <span class="k">struct</span> <span class="p">{</span>
    <span class="n">size_t</span> <span class="n">size</span><span class="p">;</span>       <span class="c1">//记录已经存下的键值对数目
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">capacity</span><span class="p">;</span>   <span class="c1">//记录表长
</span><span class="c1"></span>    <span class="n">Node</span><span class="o">**</span> <span class="n">buckets</span><span class="p">;</span> <span class="c1">//桶子：用于记录的哈希桶，桶子中每个元素是Node*
</span><span class="c1"></span><span class="p">}</span><span class="n">HashMap</span><span class="p">;</span>


<span class="cm">/*函数的声明*/</span>
<span class="n">HashMap</span><span class="o">*</span> <span class="nf">init</span><span class="p">();</span>
<span class="kt">void</span> <span class="nf">put</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">,</span><span class="n">key_t</span><span class="p">,</span><span class="n">val_t</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">,</span><span class="n">Node</span><span class="o">*</span><span class="p">);</span>                           <span class="c1">//直接把已经分配好的内存插入哈希表
</span><span class="c1"></span><span class="k">static</span> <span class="kt">void</span> <span class="nf">putVal</span><span class="p">(</span><span class="n">key_t</span><span class="p">,</span><span class="n">val_t</span><span class="p">,</span><span class="n">Node</span><span class="o">**</span><span class="p">,</span><span class="n">size_t</span><span class="o">*</span><span class="p">,</span><span class="n">size_t</span><span class="p">);</span> <span class="c1">//这个是put的委托函数,用于直接更新桶子，并更新HashMap的size
</span><span class="c1"></span><span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">getHashcode</span><span class="p">(</span><span class="n">key_t</span> <span class="p">);</span>              <span class="c1">//得到key对应的hashcode
</span><span class="c1"></span><span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">getIndex</span><span class="p">(</span><span class="n">key_t</span><span class="p">,</span><span class="n">size_t</span><span class="p">);</span>           <span class="c1">//通过桶的大小和key映射位置，算是包含了关键的哈希函数：由于C不支持泛型也就无法针对不同类型作出不同的哈希了，我这里默认key为int
</span><span class="c1"></span><span class="k">static</span> <span class="kt">void</span> <span class="nf">resize</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">);</span>                          <span class="c1">//如果插入的元素过多，*2进行重新哈希分配
</span><span class="c1"></span><span class="k">static</span> <span class="kt">void</span> <span class="nf">rehash</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">,</span><span class="n">Node</span><span class="o">**</span><span class="p">);</span>                          <span class="c1">//重新设置长度则需要重新哈希一些key的位置
</span><span class="c1"></span><span class="n">val_t</span><span class="o">*</span> <span class="nf">get</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">,</span><span class="n">key_t</span><span class="p">);</span>                            <span class="c1">//得到key对应的val
</span><span class="c1"></span><span class="k">static</span> <span class="kt">void</span> <span class="nf">del_nodes</span><span class="p">(</span><span class="n">Node</span><span class="o">*</span><span class="p">);</span>                          <span class="c1">//把单个链表销毁
</span><span class="c1"></span><span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">);</span>                                <span class="c1">//把哈希表的内存销毁
</span><span class="c1"></span>
<span class="cm">/*函数实现*/</span>
<span class="n">HashMap</span><span class="o">*</span> <span class="nf">init</span><span class="p">(){</span>    <span class="c1">//初始化得到一个哈希表
</span><span class="c1"></span>    <span class="n">HashMap</span> <span class="o">*</span> <span class="n">ret</span> <span class="o">=</span> <span class="p">(</span><span class="n">HashMap</span><span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">HashMap</span><span class="p">));</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">ret</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">);</span>
    <span class="n">ret</span><span class="o">-&gt;</span><span class="n">size</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">ret</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">=</span> <span class="n">DEFAULT_CAPACITY</span><span class="p">;</span>
    <span class="n">ret</span><span class="o">-&gt;</span><span class="n">buckets</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span><span class="o">**</span><span class="p">)</span><span class="n">calloc</span><span class="p">(</span><span class="n">DEFAULT_CAPACITY</span><span class="p">,</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span><span class="o">*</span><span class="p">));</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">ret</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">ret</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span><span class="p">,</span><span class="n">Node</span><span class="o">*</span> <span class="n">node</span><span class="p">){</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">map</span><span class="o">!=</span><span class="nb">NULL</span><span class="o">&amp;&amp;</span><span class="n">node</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">);</span>
    <span class="n">size_t</span> <span class="n">index</span> <span class="o">=</span> <span class="n">getIndex</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span><span class="p">,</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">);</span>
    <span class="k">if</span><span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span><span class="o">==</span><span class="nb">NULL</span><span class="p">){</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">node</span><span class="p">;</span>
    <span class="p">}</span><span class="k">else</span><span class="p">{</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
        <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">node</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">put</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span><span class="p">,</span><span class="n">key_t</span> <span class="n">key</span><span class="p">,</span><span class="n">val_t</span> <span class="n">val</span><span class="p">){</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">map</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="c1">//判断是否需要扩容
</span><span class="c1"></span>    <span class="k">if</span><span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">size</span> <span class="o">&gt;=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="o">*</span><span class="n">factor</span><span class="p">)</span> <span class="n">resize</span><span class="p">(</span><span class="n">map</span><span class="p">);</span>
    <span class="n">putVal</span><span class="p">(</span><span class="n">key</span><span class="p">,</span><span class="n">val</span><span class="p">,</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">,</span><span class="o">&amp;</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">size</span><span class="p">,</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">getHashcode</span><span class="p">(</span><span class="n">key_t</span> <span class="n">key</span><span class="p">){</span>
    <span class="k">return</span> <span class="n">key</span> <span class="o">^</span> <span class="p">(</span><span class="n">key</span><span class="o">&gt;&gt;</span><span class="mi">16</span><span class="p">);</span><span class="c1">//这是32位数的扰动函数
</span><span class="c1"></span><span class="p">}</span>
<span class="k">static</span> <span class="kr">inline</span> <span class="n">size_t</span> <span class="nf">getIndex</span><span class="p">(</span><span class="n">key_t</span> <span class="n">key</span><span class="p">,</span><span class="n">size_t</span> <span class="n">bucket_size</span><span class="p">){</span><span class="c1">//由于bucketsize一定是2的次方，所以size-1和key相与得到的就是下标
</span><span class="c1"></span>    <span class="k">return</span> <span class="n">getHashcode</span><span class="p">(</span><span class="n">key</span><span class="p">)</span><span class="o">&amp;</span><span class="p">(</span><span class="n">bucket_size</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">static</span> <span class="kt">void</span> <span class="nf">putVal</span><span class="p">(</span><span class="n">key_t</span> <span class="n">key</span><span class="p">,</span><span class="n">val_t</span> <span class="n">val</span><span class="p">,</span><span class="n">Node</span><span class="o">**</span> <span class="n">buckets</span><span class="p">,</span><span class="n">size_t</span><span class="o">*</span> <span class="n">returnSize</span><span class="p">,</span><span class="n">size_t</span> <span class="n">bucketSize</span><span class="p">){</span>
    <span class="c1">//获取位置
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">index</span> <span class="o">=</span> <span class="n">getIndex</span><span class="p">(</span><span class="n">key</span><span class="p">,</span><span class="n">bucketSize</span><span class="p">);</span>
    <span class="n">Node</span> <span class="o">*</span> <span class="n">node</span> <span class="o">=</span> <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
    <span class="k">if</span><span class="p">(</span><span class="n">node</span><span class="o">==</span><span class="nb">NULL</span><span class="p">){</span><span class="c1">//插入位置为空
</span><span class="c1"></span>        <span class="n">node</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span><span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span><span class="p">));</span>
        <span class="n">assert</span><span class="p">(</span><span class="n">node</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">);</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span> <span class="o">=</span> <span class="n">key</span><span class="p">;</span>
        <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">node</span><span class="p">;</span>
        <span class="p">(</span><span class="o">*</span><span class="n">returnSize</span><span class="p">)</span><span class="o">++</span><span class="p">;</span>    <span class="c1">//哈希表内的元素增加
</span><span class="c1"></span>        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="c1">//插入位置不为空，说明发生冲突，使用链地址法，遍历链表
</span><span class="c1"></span>    <span class="k">while</span> <span class="p">(</span><span class="n">node</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">){</span>
        <span class="c1">//如果key相同就覆盖
</span><span class="c1"></span>        <span class="k">if</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span><span class="o">==</span><span class="n">key</span><span class="p">){</span>
            <span class="n">node</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
            <span class="k">return</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">node</span> <span class="o">=</span> <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="c1">//当前的key不在链表中，则插入链表头部
</span><span class="c1"></span>    <span class="n">Node</span><span class="o">*</span> <span class="n">newNode</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span><span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span><span class="p">));</span>
    <span class="n">assert</span><span class="p">(</span><span class="n">newNode</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="n">newNode</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
    <span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">newNode</span><span class="p">;</span>
    <span class="p">(</span><span class="o">*</span><span class="n">returnSize</span><span class="p">)</span><span class="o">++</span><span class="p">;</span> <span class="c1">//哈希表内元素增加
</span><span class="c1"></span><span class="p">}</span>


<span class="k">static</span> <span class="kt">void</span> <span class="nf">resize</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span><span class="p">){</span>
    <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">&lt;&lt;=</span> <span class="mi">1</span><span class="p">;</span>            <span class="c1">//扩大两倍容量，相当于左移一位
</span><span class="c1"></span>    <span class="n">Node</span> <span class="o">**</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">;</span>     <span class="c1">//存下之前的内存地址
</span><span class="c1"></span>    <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span> <span class="o">=</span> <span class="p">(</span><span class="n">Node</span><span class="o">**</span><span class="p">)</span><span class="n">calloc</span><span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">,</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Node</span><span class="o">*</span><span class="p">));</span> <span class="c1">//重新分配
</span><span class="c1"></span>    <span class="n">assert</span><span class="p">(</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">);</span>
    <span class="n">rehash</span><span class="p">(</span><span class="n">map</span><span class="p">,</span><span class="n">tmp</span><span class="p">);</span><span class="c1">//重新哈希处理
</span><span class="c1"></span>    <span class="n">free</span><span class="p">(</span><span class="n">tmp</span><span class="p">);</span>                                          <span class="c1">//释放之前的内存
</span><span class="c1"></span><span class="p">}</span>


<span class="k">static</span> <span class="kt">void</span> <span class="nf">rehash</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span><span class="p">,</span><span class="n">Node</span><span class="o">**</span> <span class="n">preTable</span><span class="p">){</span><span class="c1">//采取java1.7的方式进行rehash也就是最简单直接的直接重新哈希插入
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">preCap</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="c1">//改变前的有效区域
</span><span class="c1"></span>    <span class="k">for</span><span class="p">(</span><span class="n">size_t</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">preCap</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">preTable</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">){</span><span class="c1">//判断对应的key是否需要重新换位置,如果对最新掩码多出来的1敏感则需要rehash
</span><span class="c1"></span>            <span class="n">Node</span> <span class="o">*</span><span class="n">preNode</span><span class="p">;</span>
            <span class="n">Node</span> <span class="o">*</span><span class="n">curNode</span> <span class="o">=</span> <span class="n">preTable</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">curNode</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">){</span>
                <span class="n">preNode</span> <span class="o">=</span> <span class="n">curNode</span><span class="p">;</span>
                <span class="n">curNode</span> <span class="o">=</span> <span class="n">curNode</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
                <span class="n">insert</span><span class="p">(</span><span class="n">map</span><span class="p">,</span><span class="n">preNode</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>


<span class="n">val_t</span><span class="o">*</span> <span class="nf">get</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span><span class="p">,</span><span class="n">key_t</span> <span class="n">key</span><span class="p">){</span><span class="c1">//前面的写好后，那么get就很好写了
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">index</span> <span class="o">=</span> <span class="n">getIndex</span><span class="p">(</span><span class="n">key</span><span class="p">,</span><span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">);</span>
    <span class="n">Node</span> <span class="o">*</span> <span class="n">node</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">[</span><span class="n">index</span><span class="p">];</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">node</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">key</span><span class="o">==</span><span class="n">key</span><span class="p">){</span>
            <span class="k">return</span> <span class="o">&amp;</span><span class="p">(</span><span class="n">node</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="n">node</span> <span class="o">=</span> <span class="n">node</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="nb">NULL</span><span class="p">;</span><span class="c1">//没找到返回NULL指针
</span><span class="c1"></span><span class="p">}</span>
<span class="k">static</span> <span class="kt">void</span> <span class="nf">del_nodes</span><span class="p">(</span><span class="n">Node</span><span class="o">*</span> <span class="n">head</span><span class="p">){</span><span class="c1">//删除单条链表
</span><span class="c1"></span>    <span class="n">Node</span><span class="o">*</span> <span class="n">pre</span><span class="p">;</span>
    <span class="n">Node</span><span class="o">*</span> <span class="n">cur</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">cur</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">){</span>
        <span class="n">pre</span> <span class="o">=</span> <span class="n">cur</span><span class="p">;</span>
        <span class="n">cur</span> <span class="o">=</span> <span class="n">cur</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
        <span class="n">free</span><span class="p">(</span><span class="n">pre</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">}</span>
<span class="kt">void</span> <span class="nf">destroy</span><span class="p">(</span><span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span><span class="p">){</span><span class="c1">//销毁整个哈希表
</span><span class="c1"></span>    <span class="n">size_t</span> <span class="n">sz</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">capacity</span><span class="p">;</span>
    <span class="n">Node</span> <span class="o">**</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">map</span><span class="o">-&gt;</span><span class="n">buckets</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="n">size_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">sz</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">tmp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">)</span>
            <span class="n">del_nodes</span><span class="p">(</span><span class="n">tmp</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="n">free</span><span class="p">(</span><span class="n">tmp</span><span class="p">);</span>
    <span class="n">free</span><span class="p">(</span><span class="n">map</span><span class="p">);</span>
<span class="p">}</span>
<span class="cp">#endif </span><span class="c1">//MY_TINY_STL_HASHMAP_C_H
</span><span class="c1"></span>



<span class="cm">/*题目测试接口*/</span> 
<span class="kt">int</span><span class="o">*</span> <span class="nf">twoSum</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">numsSize</span><span class="p">,</span> <span class="kt">int</span> <span class="n">target</span><span class="p">,</span> <span class="kt">int</span><span class="o">*</span> <span class="n">returnSize</span><span class="p">)</span> <span class="p">{</span><span class="c1">//两数之和万恶之源
</span><span class="c1"></span>    <span class="n">HashMap</span><span class="o">*</span> <span class="n">map</span> <span class="o">=</span> <span class="n">init</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">numsSize</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span><span class="o">*</span> <span class="n">t</span> <span class="o">=</span> <span class="n">get</span><span class="p">(</span><span class="n">map</span><span class="p">,</span><span class="n">target</span><span class="o">-</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">t</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">){</span>
            <span class="kt">int</span> <span class="o">*</span><span class="n">ret</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span><span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="o">*</span><span class="mi">2</span><span class="p">);</span>
            <span class="o">*</span><span class="n">returnSize</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span>
            <span class="n">ret</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="o">*</span><span class="n">t</span><span class="p">;</span>
            <span class="n">ret</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
            <span class="k">return</span> <span class="n">ret</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">put</span><span class="p">(</span><span class="n">map</span><span class="p">,</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">i</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="o">*</span><span class="n">returnSize</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">destroy</span><span class="p">(</span><span class="n">map</span><span class="p">);</span>
    <span class="k">return</span> <span class="nb">NULL</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h2 id="总结">总结</h2>
<p>通过这次手撕比较规范的哈希表的收获：</p>
<ol>
<li>更加深入的理解了哈希表的基本实现思想。</li>
<li>从LeetCode刷题无用的感觉到有用，比如时刻需要的链表增删操作。</li>
<li>有点遗憾，没能按照java1.8的思路再进一步优化哈希表。</li>
</ol>
<blockquote>
<p>看了很多大厂的面试题，现在对哈希表这块数据结构的考量是越来越严苛了，比如你如果走的 java 后端岗位，面试可能需要你回答 java HashMap 源码的相关实现部分，深挖原理，而不是死记硬背了，所以最好的学习方式就是学习源码，然后根据学到的思想自己实现一些功能。</p>
</blockquote>
<hr>
<p><strong>参考：</strong></p>
<p>[1]. 《数据结构与算法》</p>
<p>[2]. <a href="https://blog.csdn.net/zhengwangzw/article/details/104889549" target="_blank" rel="noopener noreffer">HashMap跟面试官扯了半个小时</a></p>
<p>[3]. <a href="https://blog.csdn.net/mxw2552261/article/details/91349677" target="_blank" rel="noopener noreffer">hashCode 为什么乘以 31？</a></p>
</div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/c/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/">C/C&#43;&#43;手撕哈希表详解</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-02-16</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解" data-hashtags="C/C&#43;&#43;手撕哈希表详解"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-hashtag="C/C&#43;&#43;手撕哈希表详解"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解" data-image="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解" data-description="C&#43;&#43;手撕哈希表详解"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解" data-description="C&#43;&#43;手撕哈希表详解"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/c&#43;&#43;%E6%89%8B%E6%92%95%E5%93%88%E5%B8%8C%E8%A1%A8%E8%AF%A6%E8%A7%A3/" data-title="C/C&#43;&#43;手撕哈希表详解"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/java%E8%BF%9E%E6%8E%A5%E6%95%B0%E6%8D%AE%E5%BA%93/" class="prev" rel="prev" title="Java连接数据库"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/%E9%AA%91%E5%A3%AB%E5%9C%A8%E6%A3%8B%E7%9B%98%E4%B8%8A%E7%9A%84%E6%A6%82%E7%8E%87dp%E6%A3%8B%E7%9B%98%E6%A6%82%E7%8E%87%E9%A2%98/" class="next" rel="next" title="骑士在棋盘上的概率——dp棋盘概率题">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
